#include <unordered_map>
#include <vector>
#include <iostream>
#include <algorithm>
#include <time.h>

using namespace std;

class Solution {
public:
	// 1.整理出所有数据，在进行判断
    /*unordered_map<int,vector<int>> omap;
    Solution(vector<int>& nums) {
        //sort(nums.begin(), nums.end());
        int left = 0;
        int len = nums.size();
		if(len == 1){
			omap[nums[0]].push_back(0);
			return;
		}
        int right = len-1;
        while(left < right){
            omap[nums[left]].push_back(left);
			omap[nums[right]].push_back(right);
			// cout << "left:" << left <<  " ";
			// cout << "right:" << right <<endl;
			left++;
            right--;
        }
		omap[nums[right]].push_back(right);
    }
	
	
    
    int pick(int target) {
		srand((int)time(0));
        auto targets = omap[target];
		int len = targets.size();
        if(len == 0){
            return -1;
        }
		for(auto i : targets){
			cout << i << " ";
		}
		cout << endl;
        return targets[rand()%len];
    }*/
	
	// 二分法找出数量，在找出对应次数
	/*vector<int> nums;
    Solution(vector<int> &nums) : nums(nums) {}

    int pick(int target) {
		vector<int> nums1;
		nums1.assign(nums.begin(), nums.end());
		sort(nums1.begin(), nums1.end());
		int left = 0;
		int right = nums1.size()-1;
		int cnt = 0;
		
		while(left < right){
			int mid = (left + right)/2;
			if(nums1[left] < target){
				left = mid;
			}
			if(nums1[left] > target){
				right = mid;
			}
			if(nums1[left] = target){
				cnt++;
				int newLeft = left;
				while(nums1[left] == nums1[left-1]){
					left = left-1;
					cnt++;
				}
				while(nums1[newLeft] == nums1[newLeft+1]){
					newLeft = newLeft+1;
					cnt++;
				}
				break;
			}
		}
		cout << "cnt:" << cnt << endl;		
		srand((int)time(0));
        vector<int> anss;

		
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == target) {
                anss.push_back(i);
				if(anss.size()-1 == cnt){
					break;
				}
            }
        }
		
		int index = rand()%anss.size();
		
		cout << "index:" << index << endl;
        return anss[index];
    }*/
	
	
};

int main(){
	vector<int> nums = {1,2,3,3,3};
	int target = 3;
	Solution* obj = new Solution(nums);
	int param = obj->pick(target);
	cout << "param:" << param << endl;
}